package algorithm.sort;

import java.util.Arrays;

public class quickSort {

    public static void sort(int[] arr, int l, int r) {
        if (l>=r) {
            return;
        }

        int p = partition(arr, l, r);
        sort(arr, l, p-1);
        sort(arr, p+1, r);
    }

    public static int partition(int[] arr, int start, int r) {
        int pv = arr[start];
        int i = start;
        int j = r;

        while (i < j) {
            while (i<j && arr[j] > pv)
                j--;
            while (i<j && arr[i] <= pv)
                i++;
            swap(arr, i, j);
        }
        swap(arr, start, j);
        return j;
    }

    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,51,6,7,2434,7,23,76,2,3};
        Arrays.stream(arr).forEach(x -> System.out.print(x+", "));
        System.out.println();
        sort(arr, 0 , arr.length-1);
        Arrays.stream(arr).forEach(x -> System.out.print(x+", "));
    }

}
